package msb.class05;

import org.junit.Assert;
import org.junit.Test;
import common.util.ArrayUtil;

/**
 * 小和问题
 * 每个数左面比他小的数累加 ->
 * 每个数的右面有几个比他大的数 ->
 * 归并过程中 记录左组比右组小时，左组数字*右组剩余个数
 */
public class Code03_SmallSum {
    public int smallSum(int[] arr) {
        return process(arr, 0, arr.length - 1);
    }

    //数据L..R有序
    public static int process(int[] arr, int L, int R) {
        int sum = 0;
        if (L == R) {
            return 0;
        }
        int mid = L + ((R - L) >> 1);
        sum += process(arr, L, mid);
        sum += process(arr, mid + 1, R);
        sum += merge(arr, L, mid, R);
        return sum;
    }

    //L..mid 与 mid+1..R进行归并
    public static int merge(int[] arr, int L, int mid, int R) {
        int leftPoint = L;
        int rightPoint = mid + 1;
        int[] tmpArr = new int[R - L + 1];
        int tmpPoint = 0;

        int sumMerge = 0;

        //左右指针越界，归并完整
        while (leftPoint <= mid || rightPoint <= R) {
            //左边指针越界，左边归并完毕，直接取右指针值
            if (leftPoint > mid) {
                tmpArr[tmpPoint++] = arr[rightPoint++];
                continue;
            }
            //右边指针越界，右边归并完毕，直接取左指针值
            if (rightPoint > R) {
                tmpArr[tmpPoint++] = arr[leftPoint++];
                continue;
            }

            //两边都没有越界，取最小值
            if (arr[leftPoint] < arr[rightPoint]) {
                sumMerge += arr[leftPoint] * (R - rightPoint + 1);
                tmpArr[tmpPoint++] = arr[leftPoint++];
            } else {
                tmpArr[tmpPoint++] = arr[rightPoint++];
            }
        }

        for (int i = 0; i < tmpArr.length; i++) {
            arr[L + i] = tmpArr[i];
        }
        return sumMerge;
    }

    @Test
    public void check() {
        for (int n = 0 ;n<100;n++){
            int[] instant = ArrayUtil.instantRandom(100, 100);
            int sumMergeExpect = 0;
            int sumMergeActual = 0;
            for (int i = 0; i < instant.length; i++) {
                for (int j = 0; j < i; j++) {
                    if (instant[j] < instant[i]) {
                        sumMergeExpect += instant[j];
                    }
                }
            }
            Code03_SmallSum code03_smallSum = new Code03_SmallSum();
            sumMergeActual = code03_smallSum.smallSum(instant);
            Assert.assertEquals(sumMergeExpect, sumMergeActual);
        }
    }


}
